package sorter;
import java.rmi.RemoteException;
import java.rmi.server.UnicastRemoteObject;

@SuppressWarnings("serial")
public class QuickSort extends UnicastRemoteObject implements ISorter {

	protected QuickSort() throws RemoteException {
		super();
	}
	
	@SuppressWarnings("rawtypes")
	public Comparable[] sort(Comparable compare[]) throws RemoteException
	{
		sort(compare, 0, compare.length-1);
		return compare;
	}

	@SuppressWarnings({ "unchecked", "rawtypes" })
	public void sort(Comparable compare[], int lo0, int hi0)
	{
		int lo = lo0;
		int hi = hi0;
		/*
		 * if the list is empty or not possible: return;
		 */
		if (lo >= hi) {
			return;
		}
		else if(lo == hi - 1) {
			/*
			 *  sort a two element list if low is higher than the high. If equal, do nothing, if smaler, do nothing.
			 *  temprorary variable T so no variable gets lost
			 */
			if (compare[lo].compareTo(compare[hi]) > 0) {
				Comparable T = compare[lo];
				compare[lo] = compare[hi];
				compare[hi] = T;
			}
			return;
		}


		/*
		 *  Pick a pivot and move it aside
		 */
		Comparable pivot = compare[(lo + hi) / 2];
		compare[(lo + hi) / 2] = compare[hi];
		compare[hi] = pivot;

		while( lo < hi ) {
			/*
			 *  Search forward from compare[lo] until an element is found that
			 *  is greater than the pivot or lo >= hi 
			 */
			while (compare[lo].compareTo(pivot) <= 0 && lo < hi) {
				lo++;
			}

			/*
			 *  Search backward from a[hi] until element is found that
			 *  is less than the pivot, or lo >= hi
			 */
			while (pivot.compareTo(compare[hi]) <= 0 && lo < hi ) {
				hi--;
			}

			/*
			 *  Swap elements compare[lo] and a[hi]
			 */
			if( lo < hi ) {
				Comparable T = compare[lo];
				compare[lo] = compare[hi];
				compare[hi] = T;
			}
		}

		/*
		 *  Put the median in the "center" of the list
		 */
		compare[hi0] = compare[hi];
		compare[hi] = pivot;

		/*
		 *  Recursive calls, elements a[lo0] to a[lo-1] are less than or
		 *  equal to pivot, elements a[hi+1] to a[hi0] are greater than
		 *  pivot.
		 */
		sort(compare, lo0, lo-1);
		sort(compare, hi+1, hi0);
	}
}
